{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count K-Subsequences of a String With Maximum Beauty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #hash-table #math #string #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #哈希表 #数学 #字符串 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countKSubsequencesWithMaxBeauty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计一个字符串的 k 子序列美丽值最大的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>k 子序列</strong>指的是 <code>s</code>&nbsp;的一个长度为 <code>k</code>&nbsp;的 <strong>子序列</strong>&nbsp;，且所有字符都是 <strong>唯一</strong>&nbsp;的，也就是说每个字符在子序列里只出现过一次。</p>\n",
    "\n",
    "<p>定义&nbsp;<code>f(c)</code>&nbsp;为字符 <code>c</code>&nbsp;在 <code>s</code>&nbsp;中出现的次数。</p>\n",
    "\n",
    "<p>k 子序列的 <strong>美丽值</strong>&nbsp;定义为这个子序列中每一个字符 <code>c</code>&nbsp;的&nbsp;<code>f(c)</code>&nbsp;之 <strong>和</strong>&nbsp;。</p>\n",
    "\n",
    "<p>比方说，<code>s = \"abbbdd\"</code>&nbsp;和&nbsp;<code>k = 2</code>&nbsp;，我们有：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>f('a') = 1</code>, <code>f('b') = 3</code>, <code>f('d') = 2</code></li>\n",
    "\t<li><code>s</code>&nbsp;的部分 k 子序列为：\n",
    "\t<ul>\n",
    "\t\t<li><code>\"<em><strong>ab</strong></em>bbdd\"</code> -&gt; <code>\"ab\"</code>&nbsp;，美丽值为&nbsp;<code>f('a') + f('b') = 4</code></li>\n",
    "\t\t<li><code>\"<em><strong>a</strong></em>bbb<em><strong>d</strong></em>d\"</code> -&gt; <code>\"ad\"</code>&nbsp;，美丽值为&nbsp;<code>f('a') + f('d') = 3</code></li>\n",
    "\t\t<li><code>\"a<em><strong>b</strong></em>bb<em><strong>d</strong></em>d\"</code> -&gt; <code>\"bd\"</code>&nbsp;，美丽值为&nbsp;<code>f('b') + f('d') = 5</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回一个整数，表示所有 <strong>k 子序列&nbsp;</strong>里面 <strong>美丽值 </strong>是&nbsp;<strong>最大值</strong>&nbsp;的子序列数目。由于答案可能很大，将结果对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;取余后返回。</p>\n",
    "\n",
    "<p>一个字符串的子序列指的是从原字符串里面删除一些字符（也可能一个字符也不删除），不改变剩下字符顺序连接得到的新字符串。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>f(c)</code> 指的是字符&nbsp;<code>c</code>&nbsp;在字符串&nbsp;<code>s</code>&nbsp;的出现次数，不是在 k 子序列里的出现次数。</li>\n",
    "\t<li>两个 k 子序列如果有任何一个字符在原字符串中的下标不同，则它们是两个不同的子序列。所以两个不同的 k 子序列可能产生相同的字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"bcca\", k = 2\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b><span style=\"white-space: normal\">s 中我们有 f('a') = 1 ，f('b') = 1 和 f('c') = 2 。</span>\n",
    "s 的 k 子序列为：\n",
    "<em><strong>bc</strong></em>ca ，美丽值为 f('b') + f('c') = 3\n",
    "<em><strong>b</strong></em>c<em><strong>c</strong></em>a ，美丽值为 f('b') + f('c') = 3\n",
    "<em><strong>b</strong></em>cc<em><strong>a</strong></em> ，美丽值为 f('b') + f('a') = 2\n",
    "b<em><strong>c</strong></em>c<em><strong>a</strong></em><strong> </strong>，美丽值为 f('c') + f('a') = 3\n",
    "bc<em><strong>ca</strong></em> ，美丽值为 f('c') + f('a') = 3\n",
    "总共有 4 个 k 子序列美丽值为最大值 3 。\n",
    "所以答案为 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"abbcd\", k = 4\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b><span style=\"white-space: normal\">s 中我们有 f('a') = 1 ，f('b') = 2&nbsp;，f('c') = 1&nbsp;和</span> f('d') = 1 。\n",
    "s 的 k 子序列为：\n",
    "<em><strong>ab</strong></em>b<em><strong>cd</strong></em> ，美丽值为 f('a') + f('b') + f('c') + f('d') = 5\n",
    "<span style=\"white-space: normal;\"><b><i>a</i></b></span>b<em><strong>bcd</strong></em> ，美丽值为 f('a') + f('b') + f('c') + f('d') = 5 \n",
    "总共有 2 个 k 子序列美丽值为最大值 5 。\n",
    "所以答案为 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= s.length</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-k-subsequences-of-a-string-with-maximum-beauty](https://leetcode.cn/problems/count-k-subsequences-of-a-string-with-maximum-beauty/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-k-subsequences-of-a-string-with-maximum-beauty](https://leetcode.cn/problems/count-k-subsequences-of-a-string-with-maximum-beauty/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"bcca\"\\n2', '\"abbcd\"\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1000000007\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        cnt = Counter(Counter(s).values())\n",
    "        used, res = 0, 1\n",
    "        for c in sorted(cnt, reverse=True):\n",
    "            used += cnt[c]\n",
    "            if used < k:\n",
    "                res *= pow(c, cnt[c], MOD)\n",
    "            else:\n",
    "                return res * pow(c, k - (used - cnt[c]), MOD) * comb(cnt[c], used - k) % MOD\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        f = Counter(s)\n",
    "        n = len(f)\n",
    "        if k > n:\n",
    "            return 0\n",
    "        g = []\n",
    "        for x in f.values():\n",
    "            g.append(x)\n",
    "        g.sort(reverse=True)\n",
    "        \n",
    "        l = r = k - 1\n",
    "        while l > 0 and g[l - 1] == g[k - 1]:\n",
    "            l -= 1\n",
    "        while r + 1 < n and g[r + 1] == g[k - 1]:\n",
    "            r += 1\n",
    "        ans, mod = 1, 10**9 + 7\n",
    "        for i in range(l):\n",
    "            ans = ans * g[i] % mod\n",
    "        # C(r - l + 1, k - l)\n",
    "        def qmi(a, p, mod):\n",
    "            res = 1\n",
    "            while p:\n",
    "                if p & 1:\n",
    "                    res = res * a % mod\n",
    "                a = a * a % mod\n",
    "                p >>= 1\n",
    "            return res\n",
    "        infact = [0] * (n + 1)\n",
    "        fact = [0] * (n + 1)\n",
    "        fact[0] = infact[0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            fact[i] = fact[i - 1] * i % mod\n",
    "            infact[i] = qmi(fact[i], mod - 2, mod)\n",
    "        a, b = r - l + 1, k - l\n",
    "        c = fact[a] % mod * infact[a - b] * infact[b] % mod\n",
    "        ans = ans * c * qmi(g[k - 1], b, mod) % mod\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        M = 10**9 + 7\n",
    "        n = len(s)\n",
    "        cnt = Counter(s).most_common()\n",
    "        if k > len(cnt):\n",
    "            return 0\n",
    "        s = 1\n",
    "        t = cnt[k - 1][1]\n",
    "        d = 0\n",
    "        for i in range(len(cnt)):\n",
    "            if cnt[i][1] > t:\n",
    "                s = s * cnt[i][1] % M\n",
    "                k -= 1\n",
    "            elif cnt[i][1] == t:\n",
    "                d += 1\n",
    "        return s * pow(t, k, M) % M * math.comb(d, k) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "import math\n",
    "from collections import Counter\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @lru_cache\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        table = Counter(s)\n",
    "        if len(table) < k:\n",
    "            return 0\n",
    "        mod = int(1e9 + 7)\n",
    "        selected = list(sorted(table.values(), reverse=True))\n",
    "        table = Counter(selected)\n",
    "        selected = Counter(selected[:k])\n",
    "        ans = 1\n",
    "        print(selected, table)\n",
    "        for val, cnt in selected.items():\n",
    "            tot = table[val]\n",
    "            res = math.comb(tot, cnt) % mod * pow(val, cnt, mod) % mod\n",
    "            ans = ans * res % mod\n",
    "            print(cnt, res, tot)\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(Solution.countKSubsequencesWithMaxBeauty(None, \"bcca\", 2))\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod=10**9+7\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        c=Counter(s)\n",
    "        y=\"abcdefghijklmnopqrstuvwxyz\"\n",
    "        @cache\n",
    "        def f(i,j)->(int,int):\n",
    "            if j==0:\n",
    "                return 0,1\n",
    "            if i==26:return 0,0\n",
    "            rmx,rcnt=f(i+1,j)\n",
    "            lmx,lcnt=f(i+1,j-1)\n",
    "            x=y[i]\n",
    "            lmx+=c[x]\n",
    "            lcnt*=c[x]\n",
    "            lcnt%=mod\n",
    "            if rmx>lmx:\n",
    "                return rmx,rcnt%mod\n",
    "            elif rmx<lmx:\n",
    "                return lmx,lcnt%mod\n",
    "            return lmx,(lcnt+rcnt)%mod\n",
    "\n",
    "        return f(0,k)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        num_freq_counter = Counter([c for c in s])\n",
    "        freq_num_cnt_counter = Counter(num_freq_counter.values())\n",
    "        sorted_freq_num_cnt_items = sorted(freq_num_cnt_counter.items(), reverse = True)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans, index = 1, 0\n",
    "        if len(num_freq_counter) < k:\n",
    "            return 0\n",
    "        while k > 0:\n",
    "            freq,num_cnt = sorted_freq_num_cnt_items[index]\n",
    "            index += 1\n",
    "            if num_cnt >= k:\n",
    "                return ans * pow(freq, k, MOD) * comb(num_cnt, k) % MOD\n",
    "            else:\n",
    "                ans *= pow(freq, num_cnt, MOD)\n",
    "            k -= num_cnt\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        C = Counter(list(s))\n",
    "        items = list(C.items())\n",
    "        items.sort(key=lambda x: -x[1])\n",
    "        res = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        if k > len(items): return 0\n",
    "        mi = items[k - 1][1]\n",
    "        cho, unc = 0, 0\n",
    "        for i in range(len(items)):\n",
    "            if items[i][1] == mi:\n",
    "                if i <= k - 1:\n",
    "                    cho += 1\n",
    "                else:\n",
    "                    unc += 1\n",
    "        for i in range(k):\n",
    "            res *= items[i][1]\n",
    "            res %= mod\n",
    "        R = 1\n",
    "        for i in range(cho + unc, unc, -1):\n",
    "            R *= i\n",
    "        for i in range(1, cho + 1):\n",
    "            R //= i\n",
    "        R %= mod\n",
    "        res = res * R % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        if k > 26:\n",
    "            return 0\n",
    "        \n",
    "        f = Counter(s)\n",
    "        mx = 0\n",
    "        combs = list()\n",
    "        for sub in combinations(f.keys(), k):\n",
    "            x = sum(f[c] for c in sub)\n",
    "            if x > mx:\n",
    "                mx = x\n",
    "                combs.clear()\n",
    "            if x == mx:\n",
    "                combs.append(sub)\n",
    "        ans = 0\n",
    "        for sub in combs:\n",
    "            ans += reduce(operator.mul, (f[c] for c in sub), 1)\n",
    "        return ans % MOD\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9 + 7\n",
    "\n",
    "from collections import Counter\n",
    "import math\n",
    "\n",
    "factors = [1]\n",
    "for i in range(1, 10**5+1):\n",
    "    factors.append(factors[-1] * i % M)\n",
    "\n",
    "# print(factors[:10])\n",
    "\n",
    "def combination(n, r):\n",
    "    # print(factors[n], factors[r])\n",
    "    return factors[n] * pow(factors[n-r], M-2, M) * pow(factors[r], M-2, M) % M\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        cnt = Counter(s)\n",
    "        if k > len(cnt):\n",
    "            return 0\n",
    "        vals = sorted(list(cnt.values()), reverse=True)\n",
    "        selected = len([i for i in vals[:k] if i == vals[k-1]])\n",
    "        total = selected + len([i for i in vals[k:] if i == vals[k-1]])\n",
    "        # print(total ,selected)\n",
    "        res = 1\n",
    "        for i in vals[:k-selected]:\n",
    "            res *= i\n",
    "            res %= M\n",
    "        res *= math.comb(total, selected)\n",
    "        # print(combination(total, selected))\n",
    "        res %= M\n",
    "        # res *= combination(total, selected)\n",
    "        res *= pow(vals[k-1], selected, M)\n",
    "        res %= M\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        MOD = 10**9 + 7 \n",
    "        cnt = Counter(s)\n",
    "        if len(cnt) < k:return 0\n",
    "        \n",
    "        nums = sorted(cnt.keys(), key=lambda x:cnt[x], reverse=True)\n",
    "        def deal(s:  list[str]) -> list[list[str]]:\n",
    "            ans = [[]]\n",
    "            p = 0\n",
    "            pre = 0\n",
    "            for v in s:\n",
    "                if not pre or cnt[v] == pre:\n",
    "                    ans[p].append(v)\n",
    "                else:\n",
    "                    p += 1\n",
    "                    ans.append([])\n",
    "                    ans[p].append(v)\n",
    "                pre = cnt[v]\n",
    "            return ans\n",
    "        \n",
    "        def getsubs(pre:  str, s: list[str], k: int) -> list[str]:\n",
    "            ans = []\n",
    "            n = len(s)\n",
    "            def dfs(i, cur):\n",
    "                if len(cur) == k:\n",
    "                    ans.append(pre + ''.join(cur))\n",
    "                    return\n",
    "                if i >= n:\n",
    "                    return\n",
    "\n",
    "                for j in range(i, n):\n",
    "                    cur.append(s[j])\n",
    "                    dfs(j + 1, cur)\n",
    "                    cur.pop()\n",
    "            dfs(0, [])\n",
    "            return ans\n",
    "        \n",
    "        def func(s: str) -> int:\n",
    "            ans = 1\n",
    "            for v in s:\n",
    "                ans *= cnt[v]\n",
    "                ans %= MOD\n",
    "            return ans\n",
    "            \n",
    "                \n",
    "        tmp = []\n",
    "        g = deal(nums)    \n",
    "        cur = 0\n",
    "        pre = \"\"\n",
    "        p = 0\n",
    "        while cur < k:\n",
    "            if len(g[p]) + cur <= k:\n",
    "                pre += ''.join(g[p])\n",
    "                cur += len(g[p])\n",
    "                p += 1\n",
    "            else:\n",
    "                tmp = getsubs(pre, g[p], k - cur)\n",
    "                break\n",
    "        \n",
    "        if not tmp:tmp = [pre]\n",
    "        ans = 0\n",
    "        for s in tmp:\n",
    "            ans += func(s)\n",
    "            ans %= MOD\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        abc = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        h = {x: i for i, x in enumerate(abc)}\n",
    "        mod = 10 ** 9 + 7\n",
    "        cnt = Counter(s)\n",
    "        a = defaultdict(list)\n",
    "        for i, x in cnt.items():\n",
    "            a[x].append(i)\n",
    "        kk = k\n",
    "        aa = sorted(a.items())\n",
    "        res = []\n",
    "        b = 0\n",
    "        while aa and kk:\n",
    "            if len(aa[-1][1]) <= kk:\n",
    "                for i in aa[-1][1]:\n",
    "                    b ^= 1 << h[i]\n",
    "                kk -= len(aa[-1][1])\n",
    "                aa.pop()\n",
    "            else:\n",
    "                for i in range(1 << len(aa[-1][1])):\n",
    "                    if bin(i).count('1') == kk:\n",
    "                        lin = 0\n",
    "                        for j in range(len(aa[-1][1])):\n",
    "                            if i & (1 << j):\n",
    "                                lin ^= 1 << h[aa[-1][1][j]]\n",
    "                        res.append(b ^ lin)\n",
    "                break\n",
    "        if not kk: res.append(b)\n",
    "        res = set(res)\n",
    "        s = [h[x] for x in s]\n",
    "        cnt = Counter(s)\n",
    "        ans = 0\n",
    "        for i in res:\n",
    "            lin = 1\n",
    "            kk = k - bin(i).count('1')\n",
    "            c = 0\n",
    "            for j in range(26):\n",
    "                if i & (1 << j):\n",
    "                    c += cnt[j] - 1\n",
    "            if c: lin *= pow(c,kk, mod)\n",
    "            for j in range(26):\n",
    "                if i & (1 << j):\n",
    "                    lin *= cnt[j]\n",
    "                    lin %= mod\n",
    "            ans += lin\n",
    "            ans %= mod\n",
    "        return ans\n",
    "                    \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        d1 = Counter(s)\n",
    "        if len(d1)<k:\n",
    "            return 0\n",
    "        d2 = Counter(list(d1.values()))\n",
    "        # print(d1,d2)\n",
    "        \n",
    "        ans = 1\n",
    "        for key2 in sorted(list(d2.keys()), reverse=True):\n",
    "            if d2[key2]<=k:\n",
    "                ans *= pow(key2, d2[key2], MOD)\n",
    "                ans%=MOD\n",
    "                k-=d2[key2]\n",
    "            else:\n",
    "                ans *= pow(key2, k, MOD)\n",
    "                ans%=MOD\n",
    "                break\n",
    "        avail = [x for x in d1 if d1[x]==key2 ]\n",
    "        n = len(list(itertools.combinations(avail,k)))\n",
    "        ans = (ans*n)%MOD\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        cc = Counter(s)\n",
    "        if k > len(cc):\n",
    "            return 0\n",
    "        p = sorted([(cc[c], c) for c in cc], reverse=True)\n",
    "        m = sum(x for x, y in p[:k])\n",
    "        f = Counter()\n",
    "        f[0, 0] = 1\n",
    "        for x, y in p:\n",
    "            ff = f.copy()\n",
    "            for c, v in ff:\n",
    "                if c < k:\n",
    "                    f[c + 1, v + x] += ff[c, v] * x % MOD\n",
    "                    if f[c + 1, v + x] >= MOD:\n",
    "                        f[c + 1, v + x] -= MOD\n",
    "        return f[k, m]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        f = Counter(s)\n",
    "        if k > len(f):\n",
    "            return 0\n",
    "\n",
    "        mx = 0\n",
    "        cand = []\n",
    "        for letters in combinations(f.keys(), k):\n",
    "            tot = 0\n",
    "            for c in letters:\n",
    "                tot += f[c]\n",
    "            if tot > mx:\n",
    "                mx = tot\n",
    "                cand = []\n",
    "                cand.append(list(letters))\n",
    "            elif tot == mx:\n",
    "                cand.append(list(letters))\n",
    "        \n",
    "        ans = 0\n",
    "        for letters in cand:\n",
    "            cnt = 1\n",
    "            for c in letters:\n",
    "                cnt *= f[c]\n",
    "                cnt %= MOD\n",
    "            ans += cnt\n",
    "            ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        M = 10**9 + 7\n",
    "        n = len(s)\n",
    "        m = defaultdict(int)\n",
    "        for c in s:\n",
    "            m[c] += 1\n",
    "        if len(m) < k:\n",
    "            return 0\n",
    "        count =list(m.values())\n",
    "        count.sort(reverse=True)\n",
    "        len_count = len(count)\n",
    "        beauty = sum(count[:k])\n",
    "\n",
    "        suffixSum = [0] * n\n",
    "        temp = 0\n",
    "        for i in range(len_count-1, -1, -1):\n",
    "            temp += count[i]\n",
    "            suffixSum[i] = temp\n",
    "\n",
    "\n",
    "        def dfs(start, picked, target):\n",
    "            if picked > k:\n",
    "                return 0\n",
    "            if target < 0:\n",
    "                return 0\n",
    "            if picked == k and target == 0:\n",
    "                return 1\n",
    "            if start < len_count and target > suffixSum[start]:\n",
    "                return 0\n",
    "  \n",
    "            res = 0\n",
    "            for i in range(start, len_count):\n",
    "                res += (count[i] * dfs(i + 1, picked + 1, target - count[i]) % M)\n",
    "            return res % M\n",
    "\n",
    "        return dfs(0, 0, beauty) % M\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 求组合数\n",
    "# mod为素数且0<=n,k<min(mod,1e7)\n",
    "\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Enumeration:\n",
    "    __slots__ = (\"_fac\", \"_ifac\", \"_inv\", \"_mod\")\n",
    "\n",
    "    def __init__(self, size: int, mod: int) -> None:\n",
    "        self._mod = mod\n",
    "        self._fac = [1]\n",
    "        self._ifac = [1]\n",
    "        self._inv = [1]\n",
    "        self._expand(size)\n",
    "\n",
    "    def fac(self, k: int) -> int:\n",
    "        self._expand(k)\n",
    "        return self._fac[k]\n",
    "\n",
    "    def ifac(self, k: int) -> int:\n",
    "        self._expand(k)\n",
    "        return self._ifac[k]\n",
    "\n",
    "    def inv(self, k: int) -> int:\n",
    "        \"\"\"模逆元\"\"\"\n",
    "        self._expand(k)\n",
    "        return self._inv[k]\n",
    "\n",
    "    def C(self, n: int, k: int) -> int:\n",
    "        if n < 0 or k < 0 or n < k:\n",
    "            return 0\n",
    "        mod = self._mod\n",
    "        return self.fac(n) * self.ifac(k) % mod * self.ifac(n - k) % mod\n",
    "\n",
    "    def P(self, n: int, k: int) -> int:\n",
    "        if n < 0 or k < 0 or n < k:\n",
    "            return 0\n",
    "        mod = self._mod\n",
    "        return self.fac(n) * self.ifac(n - k) % mod\n",
    "\n",
    "    def H(self, n: int, k: int) -> int:\n",
    "        \"\"\"可重复选取元素的组合数\"\"\"\n",
    "        if n == 0:\n",
    "            return 1 if k == 0 else 0\n",
    "        return self.C(n + k - 1, k)\n",
    "\n",
    "    def put(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个相同的球放入k个不同的盒子(盒子可放任意个球)的方案数.\"\"\"\n",
    "        return self.C(n + k - 1, n)\n",
    "\n",
    "    def catalan(self, n: int) -> int:\n",
    "        \"\"\"卡特兰数\"\"\"\n",
    "        return self.C(2 * n, n) * self.inv(n + 1) % self._mod\n",
    "\n",
    "    def _expand(self, size: int) -> None:\n",
    "        size = min(size, self._mod - 1)\n",
    "        if len(self._fac) < size + 1:\n",
    "            mod = self._mod\n",
    "            preSize = len(self._fac)\n",
    "            diff = size + 1 - preSize\n",
    "            self._fac += [1] * diff\n",
    "            self._ifac += [1] * diff\n",
    "            self._inv += [1] * diff\n",
    "            for i in range(preSize, size + 1):\n",
    "                self._fac[i] = self._fac[i - 1] * i % mod\n",
    "            self._ifac[size] = pow(self._fac[size], mod - 2, mod)  # !modInv\n",
    "            for i in range(size - 1, preSize - 1, -1):\n",
    "                self._ifac[i] = self._ifac[i + 1] * (i + 1) % mod\n",
    "            for i in range(preSize, size + 1):\n",
    "                self._inv[i] = self._ifac[i] * self._fac[i - 1] % mod\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    MOD = int(1e9 + 7)\n",
    "    C = Enumeration(size=int(1e5), mod=MOD)\n",
    "\n",
    "    # 统计一个字符串的 k 子序列美丽值最大的数目\n",
    "    class Solution:\n",
    "        def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "            MOD = int(1e9 + 7)\n",
    "            counter = Counter(s)\n",
    "            if len(counter) < k:\n",
    "                return 0\n",
    "\n",
    "            freqCounter = Counter(counter.values())\n",
    "            items = sorted(freqCounter.items(), key=lambda x: -x[0])\n",
    "            # print(items)  # \"abcdd\" -> [(2, 1), (1, 3)]\n",
    "            res = 1\n",
    "            remain = k\n",
    "            for freq, sameCount in items:\n",
    "                if remain <= 0:\n",
    "                    break\n",
    "                min_ = min(remain, sameCount)\n",
    "                res *= C.C(sameCount, min_) * pow(freq, min_, MOD)\n",
    "                res %= MOD\n",
    "                remain -= min_\n",
    "\n",
    "            return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def qmi(a, b, c):\n",
    "    res = 1\n",
    "    while b:\n",
    "        if b & 1: res = res * a % c\n",
    "        b >>= 1\n",
    "        a = a * a % c\n",
    "    \n",
    "    return res\n",
    "\n",
    "N = 200010\n",
    "fact = [0] * N\n",
    "infact = [0] * N\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "fact[0] = infact[0] = 1\n",
    "\n",
    "for i in range(1, N):\n",
    "    fact[i] = fact[i-1] * i % MOD\n",
    "    infact[i] = infact[i-1] * qmi(i, MOD-2, MOD) % MOD\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        def C(a, b):\n",
    "            # print(a, b)\n",
    "            return fact[a] * infact[b] * infact[a-b] % MOD\n",
    "        a = [0] * 26\n",
    "        for x in s:\n",
    "            a[ord(x) - ord('a')] += 1\n",
    "        \n",
    "        t = 0\n",
    "        for i in range(26):\n",
    "            if a[i]: t += 1\n",
    "        if k > t: return 0\n",
    "        \n",
    "        d = defaultdict(int)\n",
    "        for i in range(26):\n",
    "            if a[i]:\n",
    "                d[a[i]] += 1\n",
    "        \n",
    "        a1 = []\n",
    "        for x in d:\n",
    "            a1.append((x, d[x]))\n",
    "        a1.sort(reverse=True)\n",
    "        \n",
    "        res = 1\n",
    "        v = 0\n",
    "        i = 0\n",
    "        # print(a1)\n",
    "        while v < k and i < len(a1):\n",
    "            t = a1[i][1]\n",
    "            if v + t <= k:\n",
    "                for _ in range(t):\n",
    "                    res = res * a1[i][0] % MOD \n",
    "                    v += 1\n",
    "            else:\n",
    "                res = res * C(t, k-v) % MOD\n",
    "                for _ in range(k-v):\n",
    "                    res = res * a1[i][0] % MOD\n",
    "                v = k\n",
    "    \n",
    "            i += 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ma = 2*10**5\n",
    "mod = 10**9+7\n",
    "fac, inv = [1]*(ma+1), [1]*(ma+1)\n",
    "for i in range(1,ma+1):\n",
    "    fac[i] = fac[i-1]*i%mod\n",
    "    inv[i] = pow(fac[i],-1,mod)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        ct = Counter(Counter(s).values())\n",
    "        res = 1\n",
    "        for x in sorted(ct)[::-1]:\n",
    "            w = ct[x]\n",
    "            a = min(w,k)\n",
    "            res = res*pow(x,a,mod)*fac[w]*inv[a]*inv[w-a]%mod\n",
    "            k -= a\n",
    "        return 0 if k else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "import numpy as np\n",
    "import math\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        def comb(n: int, r: int) -> int: \n",
    "            if r > n:\n",
    "                return 0\n",
    "            if r > n - r:\n",
    "                r = n - r\n",
    "            c = 1\n",
    "            for i in range(r):\n",
    "                c = c * (n - i) // (i + 1)\n",
    "            return c\n",
    "        \n",
    "        count = Counter(s)\n",
    "        freqs = sorted((c for _, c in count.items()), reverse=True)\n",
    "        # print(freqs)\n",
    "        if len(freqs) < k:\n",
    "            return 0\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        min_freq_k = freqs[k - 1]\n",
    "        larger_count = len([i for i in freqs[:k] if i > min_freq_k])\n",
    "        equal_count_before_k = k - larger_count\n",
    "        equal_count_after_k = len([i for i in freqs[k:] if i == min_freq_k])\n",
    "        res = 1\n",
    "        for i in range(larger_count):\n",
    "            res *= freqs[i]\n",
    "        rest = min_freq_k ** equal_count_before_k * comb(equal_count_before_k + equal_count_after_k, equal_count_before_k)\n",
    "\n",
    "        return res * rest % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        # 长度为k的子序列\n",
    "        if k > 26:\n",
    "            return 0\n",
    "        cnt = sorted(Counter(s).values(), reverse=True)\n",
    "        n = len(cnt)\n",
    "        if len(cnt) < k:\n",
    "            return 0\n",
    "        tar = 0\n",
    "        for i in range(k):\n",
    "            tar += cnt[i]\n",
    "        @cache\n",
    "        def dfs(index, rest, tar):\n",
    "            if rest == 0:\n",
    "                return 1 if tar == 0 else 0\n",
    "            if index == n:\n",
    "                return 0\n",
    "            res = dfs(index + 1, rest, tar)\n",
    "            res += dfs(index + 1, rest - 1, tar - cnt[index]) * cnt[index]\n",
    "            res %= MOD\n",
    "            return res\n",
    "            \n",
    "        ans = dfs(0, k, tar) % MOD\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import groupby\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你一个字符串 s 和一个整数 k 。\n",
    "\n",
    "# k 子序列指的是 s 的一个长度为 k 的 子序列 ，且所有字符都是 唯一 的，也就是说每个字符在子序列里只出现过一次。\n",
    "\n",
    "# 定义 f(c) 为字符 c 在 s 中出现的次数。\n",
    "\n",
    "# k 子序列的 美丽值 定义为这个子序列中每一个字符 c 的 f(c) 之 和 。\n",
    "\n",
    "# 比方说，s = \"abbbdd\" 和 k = 2 ，我们有：\n",
    "\n",
    "# f('a') = 1, f('b') = 3, f('d') = 2\n",
    "# s 的部分 k 子序列为：\n",
    "# \"abbbdd\" -> \"ab\" ，美丽值为 f('a') + f('b') = 4\n",
    "# \"abbbdd\" -> \"ad\" ，美丽值为 f('a') + f('d') = 3\n",
    "# \"abbbdd\" -> \"bd\" ，美丽值为 f('b') + f('d') = 5\n",
    "# 请你返回一个整数，表示所有 k 子序列 里面 美丽值 是 最大值 的子序列数目。由于答案可能很大，将结果对 109 + 7 取余后返回。\n",
    "\n",
    "\n",
    "# 一个字符串的子序列指的是从原字符串里面删除一些字符（也可能一个字符也不删除），不改变剩下字符顺序连接得到的新字符串。\n",
    "class Enumeration:\n",
    "    __slots__ = (\"_fac\", \"_ifac\", \"_inv\", \"_mod\")\n",
    "\n",
    "    def __init__(self, size: int, mod: int) -> None:\n",
    "        self._mod = mod\n",
    "        self._fac = [1]\n",
    "        self._ifac = [1]\n",
    "        self._inv = [1]\n",
    "        self._expand(size)\n",
    "\n",
    "    def fac(self, k: int) -> int:\n",
    "        self._expand(k)\n",
    "        return self._fac[k]\n",
    "\n",
    "    def ifac(self, k: int) -> int:\n",
    "        self._expand(k)\n",
    "        return self._ifac[k]\n",
    "\n",
    "    def inv(self, k: int) -> int:\n",
    "        \"\"\"模逆元\"\"\"\n",
    "        self._expand(k)\n",
    "        return self._inv[k]\n",
    "\n",
    "    def C(self, n: int, k: int) -> int:\n",
    "        if n < 0 or k < 0 or n < k:\n",
    "            return 0\n",
    "        mod = self._mod\n",
    "        return self.fac(n) * self.ifac(k) % mod * self.ifac(n - k) % mod\n",
    "\n",
    "    def P(self, n: int, k: int) -> int:\n",
    "        if n < 0 or k < 0 or n < k:\n",
    "            return 0\n",
    "        mod = self._mod\n",
    "        return self.fac(n) * self.ifac(n - k) % mod\n",
    "\n",
    "    def H(self, n: int, k: int) -> int:\n",
    "        \"\"\"可重复选取元素的组合数\"\"\"\n",
    "        if n == 0:\n",
    "            return 1 if k == 0 else 0\n",
    "        return self.C(n + k - 1, k)\n",
    "\n",
    "    def put(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个相同的球放入k个不同的盒子(盒子可放任意个球)的方案数.\"\"\"\n",
    "        return self.C(n + k - 1, n)\n",
    "\n",
    "    def catalan(self, n: int) -> int:\n",
    "        \"\"\"卡特兰数\"\"\"\n",
    "        return self.C(2 * n, n) * self.inv(n + 1) % self._mod\n",
    "\n",
    "    def _expand(self, size: int) -> None:\n",
    "        size = min(size, self._mod - 1)\n",
    "        if len(self._fac) < size + 1:\n",
    "            mod = self._mod\n",
    "            preSize = len(self._fac)\n",
    "            diff = size + 1 - preSize\n",
    "            self._fac += [1] * diff\n",
    "            self._ifac += [1] * diff\n",
    "            self._inv += [1] * diff\n",
    "            for i in range(preSize, size + 1):\n",
    "                self._fac[i] = self._fac[i - 1] * i % mod\n",
    "            self._ifac[size] = pow(self._fac[size], mod - 2, mod)  # !modInv\n",
    "            for i in range(size - 1, preSize - 1, -1):\n",
    "                self._ifac[i] = self._ifac[i + 1] * (i + 1) % mod\n",
    "            for i in range(preSize, size + 1):\n",
    "                self._inv[i] = self._ifac[i] * self._fac[i - 1] % mod\n",
    "\n",
    "\n",
    "C = Enumeration(int(2e5 + 10), MOD)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        counter = Counter(s)\n",
    "        if k > len(counter):\n",
    "            return 0\n",
    "\n",
    "        pair = [(v, k) for k, v in counter.items()]\n",
    "        pair.sort(reverse=True)\n",
    "        groups = [(freq, len(list(group))) for freq, group in groupby(pair, lambda x: x[0])]\n",
    "        # print(groups)  # (freq, count)  [(2, 1), (1, 2)]\n",
    "        remain = k\n",
    "        ptr = 0\n",
    "        # 必须选*附加选\n",
    "        res = 1\n",
    "        while remain > 0 and ptr < len(groups):\n",
    "            curFreq, curCount = groups[ptr]\n",
    "            if remain >= curCount:\n",
    "                remain -= curCount\n",
    "                res *= pow(curFreq, curCount, MOD)\n",
    "                res %= MOD\n",
    "            else:\n",
    "                if curFreq == 1:\n",
    "                    res *= C.C(curCount * curFreq, remain)\n",
    "                    res %= MOD\n",
    "                    break\n",
    "                else:\n",
    "                    # all_ = C.C(curCount * curFreq, remain)\n",
    "                    # # 不能选同组的\n",
    "                    # for dup in range(2, remain + 1):\n",
    "                    #     all_ -= (\n",
    "                    #         curCount\n",
    "                    #         * C.C(curFreq, dup)\n",
    "                    #         * C.C((curCount - 1), remain - dup)\n",
    "                    #         * pow(curFreq, remain - dup, MOD)\n",
    "                    #     )\n",
    "                    #     all_ %= MOD\n",
    "                    res *= C.C(curCount, remain) * pow(curFreq, remain, MOD)\n",
    "                    res %= MOD\n",
    "                    break\n",
    "            ptr += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.special import comb, perm\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        count = {}\n",
    "\n",
    "        for s_i in s:\n",
    "            if s_i not in count:\n",
    "                count[s_i] = 0\n",
    "            count[s_i] += 1\n",
    "\n",
    "        if len(count) < k:\n",
    "            return 0\n",
    "\n",
    "        char_ct_lt = []\n",
    "        for char, value in count.items():\n",
    "            char_ct_lt.append([char,value])\n",
    "\n",
    "        char_ct_lt = sorted(char_ct_lt, key=lambda x: x[1])[::-1]\n",
    "\n",
    "        print('char_ct_lt = ', char_ct_lt)\n",
    "        value_count = {}\n",
    "\n",
    "        for char, value in char_ct_lt:\n",
    "            if value not in value_count:\n",
    "                value_count[value] = 0\n",
    "            value_count[value] += 1\n",
    "        \n",
    "        print(value_count)\n",
    "\n",
    "        A = 1\n",
    "        for value, count in value_count.items():\n",
    "            if k - count > 0:\n",
    "                A *= pow(value, count, 1000000007)\n",
    "                A = A % 1000000007\n",
    "                k -= count\n",
    "            else:\n",
    "                A *= pow(value, k, 1000000007)\n",
    "                A = A % 1000000007\n",
    "                A *= (comb(count, k) % 1000000007)\n",
    "                A = A % 1000000007\n",
    "                break\n",
    "        return int(A % 1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from scipy.special import perm, comb\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        mod=int(1e9+7)\n",
    "        d={}\n",
    "        for i in s:\n",
    "            d[i]=d.get(i,0)+1\n",
    "        a=list(d.values())\n",
    "        if k>len(a): return 0\n",
    "        a.sort()\n",
    "        a.reverse()\n",
    "        ans=1\n",
    "        last=0\n",
    "        for i in range(k):\n",
    "            ans*=a[i]\n",
    "            ans%=mod\n",
    "            last=a[i]\n",
    "        lastlcnt=0\n",
    "        lastrcnt=0\n",
    "        for i in range(k):\n",
    "            if a[i]==last: lastlcnt+=1\n",
    "        for i in range(k,len(a)):\n",
    "            if a[i]==last: lastrcnt+=1\n",
    "        ans*=int(comb(lastrcnt+lastlcnt,lastlcnt))\n",
    "        ans%=mod\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.special import comb\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def qpow(n, m):\n",
    "            res = 1\n",
    "            base = n\n",
    "            while m != 0:\n",
    "                if (m&1) != 0:\n",
    "                    res = res*base%MOD\n",
    "                base = base*base%MOD\n",
    "                m = m >> 1\n",
    "            return res\n",
    "\n",
    "        cnt = Counter()\n",
    "        for _,l in enumerate(s):\n",
    "            cnt[l] += 1\n",
    "            \n",
    "        cnt2 = Counter()\n",
    "        for _,v in cnt.items():\n",
    "            cnt2[v] += 1\n",
    "        \n",
    "        l = []\n",
    "        for x,v in cnt2.items():\n",
    "            l.append([x,v])\n",
    "            \n",
    "        l.sort(key = lambda z: -z[0])\n",
    "\n",
    "        ans = 1\n",
    "        i = 0\n",
    "        n = len(l)\n",
    "        while k > 0 and i < n:\n",
    "            if k >= l[i][1]:\n",
    "                ans *= (qpow(l[i][0], l[i][1]))\n",
    "                ans %= MOD\n",
    "                k -= l[i][1]\n",
    "            else:\n",
    "                ans *= (qpow(l[i][0], k) * int(comb(l[i][1], k)))\n",
    "                ans %= MOD\n",
    "                k = 0\n",
    "            i += 1\n",
    "            \n",
    "        return ans if k == 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:\n",
    "        from scipy.special import comb\n",
    "        cnt = Counter(s)\n",
    "        if len(cnt) < k:\n",
    "            return 0\n",
    "        cnt2 = Counter(cnt.values())\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 1\n",
    "        for v, c in sorted(cnt2.items(), reverse=True):\n",
    "            # print(v, c)\n",
    "            if k >= c:\n",
    "                ans = ans * pow(v, c, MOD) % MOD\n",
    "                k -= c\n",
    "                if k == 0:\n",
    "                    break\n",
    "            else:\n",
    "                ans = ans * pow(v, k, MOD) % MOD\n",
    "                ans = int(comb(c, k)) * ans % MOD \n",
    "                break\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
